/*
 * operacoes.c
 *
 *  Created on: 08/06/2011
 *      Author: Jonatas Lopes de Paiva
 *
 * Implementa operacoes.h e mais algumas funcoes
 * auxiliares
 */

#include "operacoes.h"

/*
 * Funcao que faz um pre-processamento no grafo, indexando cada um
 * dos vertices.
 * */
void preProcessa(Grafo *grafo) {
	Vertice *it = grafo->head;
	int i = 0;

	while (it != NULL) {
		it->posicao = i++;
		it = it->prox;
	}
}

/*
 * Funcao que imprime o cabecalho do arquivo.
 * */
void printCabecalho(Vertice **vertices, int tamG, FILE *file) {
	fprintf(file, "iter\t");
	fprintf(file, "C");
	int i = 0;

	for (i = 0; i < tamG; i++) {
		fprintf(file, " \t");
	}

	fprintf(file, "\tw esc\t\tw\t\t");

	for (i = 0; i < tamG; ++i) {
		fprintf(file, "%d\t", vertices[i]->rotulo);
	}

	fprintf(file, "\n\n");
}

/*
 * Funcao que imprime uma linha do arquivo.
 * */
void print(int iteracao, Vertice **c, int tamC, Vertice *escolhido, int w,
		int *dist, int tamDist, FILE *file) {
	fprintf(file, "%d\t", iteracao - 1);

	int i = 0;
	for (i = 0; i < tamC; ++i) {
		fprintf(file, "%d", c[i]->rotulo);
		if (i < tamC - 1) {
			fprintf(file, ",\t");
		}
	}

	for (i = tamC; i < tamDist; i++) {
		fprintf(file, " \t");
	}
	fprintf(file, "\t\t");
	fprintf(file, "%d\t\t", escolhido->rotulo);
	fprintf(file, "%d\t\t", w);

	for (i = 0; i < tamDist; ++i) {
		fprintf(file, "%d\t", dist[i]);
	}

	fprintf(file, "\n");
}

/*
 * Funcao que imprime os caminhos
 * */
void printAntecessor(int *antecessor, Vertice **q, int size, FILE *file) {
	fprintf(file,
			"\n\n=============================================================\n\n");
	fprintf(file, "Caminhos de v0 ate os outros vertices:\n\n");

	int i = 1;

	int* buffer = (int*) malloc(size * sizeof(int));

	for (i = 1; i < size; i++) {

		int ant = antecessor[i];
		int cont = 0;
		buffer[cont++] = q[i]->rotulo;

		while (ant != -1) {
			buffer[cont++] = ant;
			ant = antecessor[ant];
		}

		int j;

		fprintf(file, "Vertice %d: ", q[i]->rotulo);

		for (j = cont - 1; j >= 0; j--) {
			fprintf(file, "%d \t ", q[buffer[j]]->rotulo);
		}

		fprintf(file, "\n");

	}

}

/*
 * Caminho minimo
 * */
int CamMin(Grafo *grafo, char* arqSaida) {

	FILE *file = fopen(arqSaida, "w");

	if (file == NULL) {
		return -2;
	}

	Vertice **c = (Vertice**) malloc(grafo->size * (sizeof(Vertice*)));
	if (c == NULL) {
		fclose(file);
		return 0;
	}

	/*
	 * Utilizado para acessar os Vertices mais facilmente
	 * */
	Vertice **q = (Vertice**) malloc(grafo->size * (sizeof(Vertice*)));
	if (q == NULL) {
		free(c);
		fclose(file);
		return 0;
	}

	int *dist = (int*) malloc(grafo->size * (sizeof(int)));
	if (dist == NULL) {
		free(c);
		free(q);
		fclose(file);
		return 0;
	}

	/*
	 * Utilizado para marcar se um vertice ja foi inserido em C
	 * */
	int *visitado = (int*) malloc(grafo->size * (sizeof(int)));
	if (visitado == NULL) {
		free(c);
		free(q);
		free(dist);
		fclose(file);
		return 0;
	}

	/*
	 * Utilizado para marcar o caminho de v0 ate um vertice qualquer
	 * */
	int *antecessor = (int*) malloc(grafo->size * (sizeof(int)));
	if (antecessor == NULL) {
		free(visitado);
		free(c);
		free(q);
		free(dist);
		fclose(file);
		return 0;
	}

	preProcessa(grafo);

	Vertice *iterador;
	int i = 0;

	for (iterador = grafo->head; iterador != NULL; iterador = iterador->prox) {
		q[i++] = iterador;
	}

	dist[0] = 0;
	visitado[0] = 1;
	c[0] = q[0];
	antecessor[0] = -1;

	int tamC = 1;

	for (i = 1; i < grafo->size; i++) {
		dist[i] = 1000;
		visitado[i] = 0;
		antecessor[i] = -1;
	}

	printCabecalho(q, grafo->size, file);

	Aresta *it;

	/*
	 * Inicializa o vetor de distancias utilizando o campo posicao
	 * dos Vertices.
	 * */
	for (it = grafo->head->headArestas; it != NULL; it = it->prox) {
		dist[it->destino->posicao] = it->custo;
		antecessor[it->destino->posicao] = 0;
	}

	print(tamC, c, tamC, c[0], 0, dist, grafo->size, file);

	while (tamC < grafo->size) {

		int w = 1000;
		int escolhido = -1;

		/*
		 * Procura o proximo vertice a ser inserido em C
		 * Sera inserido o de menor w que ainda nao faz parte de C
		 * */
		for (i = 0; i < grafo->size; i++) {
			if (!visitado[i] && (dist[i] < w)) {
				escolhido = i;
				w = dist[i];
			}
		}

		/*
		 * Grafo disconexo
		 * */
		if (escolhido == -1) {
			fclose(file);
			free(antecessor);
			free(c);
			free(q);
			free(dist);
			free(visitado);
			return -1;
		}

		iterador = q[escolhido];
		visitado[escolhido] = 1;

		c[tamC++] = iterador;

		/*
		 * Atualiza as distancias
		 * */
		for (it = iterador->headArestas; it != NULL; it = it->prox) {
			if (dist[it->destino->posicao] > w + it->custo) {
				dist[it->destino->posicao] = w + it->custo;
				antecessor[it->destino->posicao] = escolhido;
			}
		}

		print(tamC, c, tamC, iterador, w, dist, grafo->size, file);

	}

	printAntecessor(antecessor, q, grafo->size, file);

	free(c);
	free(q);
	free(dist);
	free(visitado);
	free(antecessor);

	fclose(file);

	return 1;

}
